//
// Created by lwj12 on 24-8-27.
//

#ifndef AVLTREE_AVLTREE_H
#define AVLTREE_AVLTREE_H
#include <cassert>
#include <iostream>
using namespace std;

namespace lwj
{
    template<class K, class V>
    struct AVLTreeNode
    {
        AVLTreeNode<K, V>* _left;
        AVLTreeNode<K, V>* _right;
        AVLTreeNode<K, V>* _father;

        pair<const K, V> _kv;
        int _bf;

        AVLTreeNode(pair<K, V> kv = pair<const K, V>())
            : _kv(kv),
              _bf(0),
              _left(nullptr),
              _right(nullptr),
              _father(nullptr)
        {}
    };

    template<class K, class V, class Ptr, class Ref>
    struct AVLTreeIterator
    {
        typedef AVLTreeNode<K, V> Node;
        typedef AVLTreeIterator<K, V, Ptr, Ref> Self;

        AVLTreeIterator(Node* node)
                : _node(node)
        {}

        Self& operator++(Self it) {}

        Node* _node;
    };

    template<class K, class V, class Compare = less<pair<K, V>>>
    class AVLTree
    {
    public:
        typedef AVLTreeNode<K, V> Node;
        typedef AVLTreeIterator<K, V, pair<K, V>*, pair<K, V>&> iterator;
        typedef AVLTreeIterator<K, V, const pair<K, V>*, const pair<K, V>&> const_iterator;

        AVLTree() = default;
        AVLTree(const AVLTree<K, V>& avl) {_root = CopyNode(avl._root); Node* root = _root; CopyDate(root, avl.root);}
        template<class InputIterator>
        AVLTree(InputIterator first, InputIterator last) {while (first != last) {insert(*first); ++first;}}
        AVLTree(initializer_list<pair<K, V>> il) {for(const auto& e : il) insert(e);}

        ~AVLTree() {Destroy(_root); _root = nullptr;}

        void RotateL(Node* father);
        void RotateR(Node* father);
        void RotateLR(Node* father);
        void RotateRL(Node* father);

        //pair<iterator, bool> insert(const pair<const K, V>& val);
        bool insert(const pair<const K, V>& val);

        bool erase(const K& key);
        iterator erase(const iterator it);
        iterator erase(const iterator first, const iterator last);

        iterator find(const K& k);
        const_iterator  find(const K& k) const;

        bool check() {return _check(_root);}

    private:
        int _Height(Node* root)
        {
            if(root == nullptr) return 0;

            int heightL = _Height(root->_left) + 1;
            int heightR = _Height(root->_right) + 1;

            return heightL > heightR ? heightL : heightR;
        }

        bool _check(Node* root)
        {
            if(root == nullptr) return true;

            int heightL = _Height(root->_left);
            int heightR = _Height(root->_right);
            int diff = heightR - heightL;

            if(abs(diff) > 1)
            {
                cout << root->_kv.first << ": 高度差错误" << endl;
                return false;
            }

            if(root->_bf != diff)
            {
                cout << root->_kv.first << ": 平衡因子错误" << endl;
                return false;
            }
            return _check(root->_left) && _check(root->_right);
        }

        Node* CopyNode(Node* root)
        {
            if(root == nullptr) return nullptr;
            Node* newNode = new Node(root-> _kv);
            newNode->_left = CopyNode(root->_left);
            newNode->_right = CopyNode(root->_right);
            return newNode;
        }

        Node* CopyDate(Node* root1, Node* root2)
        {
            if(root1 == nullptr) return nullptr;
            root1->_bf = root2->_bf;
            root1 = CopyDate(root1->_left, root2->_left)->_father;
            root1 = CopyDate(root1->_right, root2->_right)->_father;
        }

        void Destroy(Node* root)
        {
            if(root == nullptr) return;
            Destroy(root->_left);
            Destroy(root->_right);
            delete root;
        }

        Node* _root = nullptr;
    };

    template<class K, class V, class Compare>
    void AVLTree<K, V, Compare>::RotateL(Node* father)
    {
        Node* subR = father->_right;
        Node* subRL = subR->_left;

        Node* fatherFather = father->_father;

        father->_father = subR;
        if(subRL) subRL->_father = father;
        father->_right = subRL;
        subR->_left = father;
        if(fatherFather)
        {
            subR->_father = fatherFather;
            if(fatherFather->_right == father) fatherFather->_right = subR;
            else fatherFather->_left = subR;
        }
        else
        {
            _root = subR;
            subR->_father = nullptr;
        }

        father->_bf = subR->_bf = 0;
    }

    template<class K, class V, class Compare>
    void AVLTree<K, V, Compare>::RotateR(Node* father)
    {
        Node* subL = father->_left;
        Node* subLR = subL->_right;

        Node* fatherFather = father->_father;

        father->_father = subL;
        if(subLR) subLR->_father = father;
        father->_left = subLR;
        subL->_right = father;
        if(fatherFather)
        {
            subL->_father = fatherFather;
            if(fatherFather->_right == father) fatherFather->_right = subL;
            else fatherFather->_left = subL;
        }
        else
        {
            _root = subL;
            subL->_father = nullptr;
        }

        father->_bf = subL->_bf = 0;
    }

    template<class K, class V, class Compare>
    void AVLTree<K, V, Compare>::RotateLR(Node* father)
    {
        Node* subL = father->_left, *subLR = subL->_right, *fatherFather = father->_father;
        int bfLR = subLR->_bf;

        RotateL(subL);
        RotateR(father);

        if(bfLR == 1)  subL->_bf = -1;
        if(bfLR == -1) father->_bf = 1;
    }

    template<class K, class V, class Compare>
    void AVLTree<K, V, Compare>::RotateRL(Node* father)
    {
        Node* subR = father->_right, *subRL = subR->_left, *fatherFather = father->_father;
        int bfRL = subRL->_bf;

        RotateR(subR);
        RotateL(father);

        if(bfRL == 1)  father->_bf = -1;
        if(bfRL == -1) subR->_bf = 1;
    }

    template<class K, class V, class Compare>
    //pair<typename AVLTree<K, V, Compare>::iterator, bool>
    bool
    AVLTree<K, V, Compare>::insert(const pair<const K, V>& val)
    {
        Node * date = new Node(val);
        if(_root == nullptr)
        {
            _root = date;
            return true;
        }
        K key = val.first;
        Node* cur = _root;
        Node* father;

        while (cur != nullptr)
        {
            if(key > cur->_kv.first)
            {
                father = cur;
                cur = cur->_right;
            }
            else if(key < cur->_kv.first)
            {
                father = cur;
                cur = cur->_left;
            }
            else
            {
                delete date;
                //return {iterator(cur), false};
                return false;
            }
        }

        if(father->_kv.first > key) father->_left = date;
        else father->_right = date;
        date->_father = father;

        cur = date;
        while (father)
        {
            if(cur == father->_left) father->_bf--;
            else father->_bf++;

            if(father->_bf == 0) break;
            else if(father->_bf == 2 || father->_bf == -2)
            {
                if(father->_bf == 2)
                {
                    if(father->_right->_bf == 1) RotateL(father);
                    else RotateRL(father);
                }
                else if(father->_bf == -2)
                {
                    if(father->_left->_bf == -1) RotateR(father);
                    else RotateLR(father);
                }
                else assert(false);
                break;
            }
            cur = father, father = father->_father;
        }

        //return {iterator(date), true};
        return true;
    }

    template<class K, class V, class Compare>
    bool AVLTree<K, V, Compare>::erase(const K & key)
    {
        assert(_root);

    }

    template<class K, class V, class Compare>
    typename AVLTree<K, V, Compare>::iterator AVLTree<K, V, Compare>::erase(const iterator it)
    {

    }

    template<class K, class V, class Compare>
    typename AVLTree<K, V, Compare>::iterator AVLTree<K, V, Compare>::erase(const iterator fast, const iterator last)
    {

    }

    template<class K, class V, class Compare>
    typename AVLTree<K, V, Compare>::iterator AVLTree<K, V, Compare>::find(const K &k)
    {

    }

    template<class K, class V, class Compare>
    typename AVLTree<K, V, Compare>::const_iterator AVLTree<K, V, Compare>::find(const K &k) const
    {

    }
}

#endif//AVLTREE_AVLTREE_H
